package com.hardy.leetcode;

/**
 * Given a string S and a string T, count the number of distinct subsequences of T in S.
 A subsequence of a string is a new string which is formed from the original string by deleting some (can be none) of the characters without disturbing the relative positions of the remaining characters. (ie,"ACE"is a subsequence of"ABCDE"while"AEC"is not).
 Here is an example:
 S ="rabbbit", T ="rabbit"
 Return3.
 * User: Ruijie Date: 2016/9/5
 */
public class DistinctSubsequences {
    public static int numDistinct1(String S,String T){
        if(S==null||T==null){
            return 0;
        }
        return res1(S,T,0,0);
    }

    private static int res1(String s, String t, int indexS, int indexT) {
        int lenS=s.length();
        int lenT=t.length();
        int sum=0;
        if(indexT>=lenT){
            return 1;
        }
        if(indexS>=lenS){
            return 0;
        }
        if(s.charAt(indexS)==t.charAt(indexT)){
            sum+=res1(s,t,indexS+1,indexT+1);
        }
        sum+=res1(s,t,indexS+1,indexT);
        return sum;
    }

    public static int numDistinct2(String S,String T){
        if(S==null||T==null){
            return 0;
        }
        if(S.length()<T.length()){
            return 0;
        }
        return res2(S,T,0,0);
    }

    private static int res2(String s, String t, int indexS, int indexT) {
        int lenS=s.length();
        int lenT=t.length();
        if(indexT>=lenT){
            return 1;
        }
        if(indexS>=lenS){
            return 0;
        }
        int sum=0;
        for(int i=indexS;i<lenS;i++){
            if(s.charAt(i)==t.charAt(indexT)){
                sum+=res2(s,t,i+1,indexT+1);
            }
        }
        return sum;
    }

    public static int numDistinct3(String S,String T){
        return 2;
    }
    public static int numDistinct4(String S,String T){
        return 3;
    }
    public static int numDistinct(String S, String T) {
        if(S==null||T==null){
            return 0;
        }
        if(S.length()<T.length()){
            return 0;
        }
        int[][] dp=new int[S.length()+1][T.length()+1];
        dp[0][0]=1;
        for(int i=0;i<S.length()+1;i++){
            dp[i][0]=1;
        }
        for(int i=1;i<S.length()+1;i++){
            for(int j=1;j<T.length()+1;j++){
                if(S.charAt(i-1)==T.charAt(j-1)){
                    dp[i][j]=dp[i-1][j-1]+dp[i-1][j];
                }else{
                    dp[i][j]=dp[i-1][j];
                }
            }
        }
        for(int row=0;row<dp.length;row++){
            for(int col=0;col<dp[0].length;col++){
                System.out.print(dp[row][col]+" ");
            }
            System.out.println();
        }
        return dp[S.length()][T.length()];
    }

    public static void main(String[] args) {
        String S="rabbbit";
        String T="rabbit";
        System.out.println(numDistinct(S,T));
        System.out.println(numDistinct1(S,T));
        System.out.println(numDistinct2(S,T));
    }
}
